home *** CD-ROM | disk | FTP | other *** search
/ Amiga Games Extra 1996 September / Amiga Games Extra CD-ROM 9-1996.iso / userbox / publicdomain / vim-4.2 / src / undo.c < prev    next >
C/C++ Source or Header  |  1996-06-09  |  27KB  |  1,057 lines
  1. /* vi:set ts=4 sw=4:
  2.  *
  3.  * VIM - Vi IMproved        by Bram Moolenaar
  4.  *
  5.  * Do ":help uganda"  in Vim to read copying and usage conditions.
  6.  * Do ":help credits" in Vim to see a list of people who contributed.
  7.  */
  8.  
  9. /*
  10.  * undo.c: multi level undo facility
  11.  *
  12.  * The saved lines are stored in a list of lists (one for each buffer):
  13.  *
  14.  * b_u_oldhead------------------------------------------------+
  15.  *                                                            |
  16.  *                                                            V
  17.  *                +--------------+    +--------------+    +--------------+
  18.  * b_u_newhead--->| u_header     |    | u_header     |    | u_header     |
  19.  *                |     uh_next------>|     uh_next------>|     uh_next---->NULL
  20.  *         NULL<--------uh_prev  |<---------uh_prev  |<---------uh_prev  |
  21.  *                |     uh_entry |    |     uh_entry |    |     uh_entry |
  22.  *                +--------|-----+    +--------|-----+    +--------|-----+
  23.  *                         |                   |                   |
  24.  *                         V                   V                   V
  25.  *                +--------------+    +--------------+    +--------------+
  26.  *                | u_entry      |    | u_entry      |    | u_entry      |
  27.  *                |     ue_next  |    |     ue_next  |    |     ue_next  |
  28.  *                +--------|-----+    +--------|-----+    +--------|-----+
  29.  *                         |                   |                   |
  30.  *                         V                   V                   V
  31.  *                +--------------+            NULL                NULL
  32.  *                | u_entry      |
  33.  *                |     ue_next  |
  34.  *                +--------|-----+
  35.  *                         |
  36.  *                         V
  37.  *                        etc.
  38.  *
  39.  * Each u_entry list contains the information for one undo or redo.
  40.  * curbuf->b_u_curhead points to the header of the last undo (the next redo),
  41.  * or is NULL if nothing has been undone.
  42.  *
  43.  * All data is allocated with u_alloc_line(), thus it will be freed as soon as
  44.  * we switch files!
  45.  */
  46.  
  47. #include "vim.h"
  48. #include "globals.h"
  49. #include "proto.h"
  50. #include "option.h"
  51.  
  52. static void u_getbot __ARGS((void));
  53. static int u_savecommon __ARGS((linenr_t, linenr_t, linenr_t));
  54. static void u_undoredo __ARGS((void));
  55. static void u_undo_end __ARGS((void));
  56. static void u_freelist __ARGS((struct u_header *));
  57. static void u_freeentry __ARGS((struct u_entry *, long));
  58.  
  59. static char_u *u_blockalloc __ARGS((long_u));
  60. static void u_free_line __ARGS((char_u *));
  61. static char_u *u_alloc_line __ARGS((unsigned));
  62. static char_u *u_save_line __ARGS((linenr_t));
  63.  
  64. static long        u_newcount, u_oldcount;
  65.  
  66. /*
  67.  * save the current line for both the "u" and "U" command
  68.  */
  69.     int
  70. u_save_cursor()
  71. {
  72.     return (u_save((linenr_t)(curwin->w_cursor.lnum - 1), (linenr_t)(curwin->w_cursor.lnum + 1)));
  73. }
  74.  
  75. /*
  76.  * Save the lines between "top" and "bot" for both the "u" and "U" command.
  77.  * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
  78.  * Returns FAIL when lines could not be saved, OK otherwise.
  79.  */
  80.     int
  81. u_save(top, bot)
  82.     linenr_t top, bot;
  83. {
  84.     if (undo_off)
  85.         return OK;
  86.  
  87.     if (top > curbuf->b_ml.ml_line_count ||
  88.                             top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  89.         return FALSE;    /* rely on caller to do error messages */
  90.  
  91.     if (top + 2 == bot)
  92.         u_saveline((linenr_t)(top + 1));
  93.  
  94.     return (u_savecommon(top, bot, (linenr_t)0));
  95. }
  96.  
  97. /*
  98.  * save the line "lnum" (used by :s command)
  99.  * The line is replaced, so the new bottom line is lnum + 1.
  100.  */
  101.     int
  102. u_savesub(lnum)
  103.     linenr_t    lnum;
  104. {
  105.     if (undo_off)
  106.         return OK;
  107.  
  108.     return (u_savecommon(lnum - 1, lnum + 1, lnum + 1));
  109. }
  110.  
  111. /*
  112.  * a new line is inserted before line "lnum" (used by :s command)
  113.  * The line is inserted, so the new bottom line is lnum + 1.
  114.  */
  115.      int
  116. u_inssub(lnum)
  117.     linenr_t    lnum;
  118. {
  119.     if (undo_off)
  120.         return OK;
  121.  
  122.     return (u_savecommon(lnum - 1, lnum, lnum + 1));
  123. }
  124.  
  125. /*
  126.  * save the lines "lnum" - "lnum" + nlines (used by delete command)
  127.  * The lines are deleted, so the new bottom line is lnum, unless the buffer
  128.  * becomes empty.
  129.  */
  130.     int
  131. u_savedel(lnum, nlines)
  132.     linenr_t    lnum;
  133.     long        nlines;
  134. {
  135.     if (undo_off)
  136.         return OK;
  137.  
  138.     return (u_savecommon(lnum - 1, lnum + nlines,
  139.                         nlines == curbuf->b_ml.ml_line_count ? 2 : lnum));
  140. }
  141.  
  142.     static int 
  143. u_savecommon(top, bot, newbot)
  144.     linenr_t top, bot;
  145.     linenr_t newbot;
  146. {
  147.     linenr_t        lnum;
  148.     long            i;
  149.     struct u_header *uhp;
  150.     struct u_entry    *uep;
  151.     long            size;
  152.  
  153.     /*
  154.      * if curbuf->b_u_synced == TRUE make a new header
  155.      */
  156.     if (curbuf->b_u_synced)
  157.     {
  158.         /*
  159.          * if we undid more than we redid, free the entry lists before and
  160.          * including curbuf->b_u_curhead
  161.          */
  162.         while (curbuf->b_u_curhead != NULL)
  163.             u_freelist(curbuf->b_u_newhead);
  164.  
  165.         /*
  166.          * free headers to keep the size right
  167.          */
  168.         while (curbuf->b_u_numhead > p_ul && curbuf->b_u_oldhead != NULL)
  169.             u_freelist(curbuf->b_u_oldhead);
  170.  
  171.         if (p_ul < 0)            /* no undo at all */
  172.             return OK;
  173.  
  174.         /*
  175.          * make a new header entry
  176.          */
  177.         uhp = (struct u_header *)u_alloc_line((unsigned)sizeof(struct u_header));
  178.         if (uhp == NULL)
  179.             goto nomem;
  180.         uhp->uh_prev = NULL;
  181.         uhp->uh_next = curbuf->b_u_newhead;
  182.         if (curbuf->b_u_newhead != NULL)
  183.             curbuf->b_u_newhead->uh_prev = uhp;
  184.         uhp->uh_entry = NULL;
  185.         uhp->uh_cursor = curwin->w_cursor;        /* save cursor pos. for undo */
  186.  
  187.         /* save changed and buffer empty flag for undo */
  188.         uhp->uh_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
  189.                        ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
  190.  
  191.         /* save named marks for undo */
  192.         vim_memmove((char *)uhp->uh_namedm, (char *)curbuf->b_namedm,
  193.                                                        sizeof(FPOS) * NMARKS); 
  194.         curbuf->b_u_newhead = uhp;
  195.         if (curbuf->b_u_oldhead == NULL)
  196.             curbuf->b_u_oldhead = uhp;
  197.         ++curbuf->b_u_numhead;
  198.     }
  199.     else    /* find line number for ue_bot for previous u_save() */
  200.         u_getbot();
  201.  
  202.     size = bot - top - 1;
  203. #if !defined(UNIX) && !defined(DJGPP) && !defined(WIN32) && !defined(__EMX__)
  204.         /*
  205.          * With Amiga and MSDOS we can't handle big undo's, because then
  206.          * u_alloc_line would have to allocate a block larger than 32K
  207.          */
  208.     if (size >= 8000)
  209.         goto nomem;
  210. #endif
  211.  
  212.     /*
  213.      * add lines in front of entry list
  214.      */
  215.     uep = (struct u_entry *)u_alloc_line((unsigned)sizeof(struct u_entry));
  216.     if (uep == NULL)
  217.         goto nomem;
  218.  
  219.     uep->ue_size = size;
  220.     uep->ue_top = top;
  221.     uep->ue_lcount = 0;
  222.     if (newbot)
  223.         uep->ue_bot = newbot;
  224.         /*
  225.          * Use 0 for ue_bot if bot is below last line.
  226.          * Otherwise we have to compute ue_bot later.
  227.          */
  228.     else if (bot > curbuf->b_ml.ml_line_count)
  229.         uep->ue_bot = 0;
  230.     else
  231.         uep->ue_lcount = curbuf->b_ml.ml_line_count;
  232.  
  233.     if (size)
  234.     {
  235.         if ((uep->ue_array = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * size))) == NULL)
  236.         {
  237.             u_freeentry(uep, 0L);
  238.             goto nomem;
  239.         }
  240.         for (i = 0, lnum = top + 1; i < size; ++i)
  241.         {
  242.             if ((uep->ue_array[i] = u_save_line(lnum++)) == NULL)
  243.             {
  244.                 u_freeentry(uep, i);
  245.                 goto nomem;
  246.             }
  247.         }
  248.     }
  249.     uep->ue_next = curbuf->b_u_newhead->uh_entry;
  250.     curbuf->b_u_newhead->uh_entry = uep;
  251.     curbuf->b_u_synced = FALSE;
  252.     return OK;
  253.  
  254. nomem:
  255.     if (ask_yesno((char_u *)"No undo possible; continue anyway", TRUE) == 'y')
  256.     {
  257.         undo_off = TRUE;            /* will be reset when character typed */
  258.         return OK;
  259.     }
  260.     do_outofmem_msg();
  261.     return FAIL;
  262. }
  263.  
  264.     void
  265. u_undo(count)
  266.     int count;
  267. {
  268.     /*
  269.      * If we get an undo command while executing a macro, we behave like the 
  270.      * original vi. If this happens twice in one macro the result will not
  271.      * be compatible.
  272.      */
  273.     if (curbuf->b_u_synced == FALSE)
  274.     {
  275.         u_sync();
  276.         count = 1;
  277.     }
  278.  
  279.     u_newcount = 0;
  280.     u_oldcount = 0;
  281.     while (count--)
  282.     {
  283.         if (curbuf->b_u_curhead == NULL)            /* first undo */
  284.             curbuf->b_u_curhead = curbuf->b_u_newhead;
  285.         else if (p_ul > 0)                            /* multi level undo */
  286.                                                     /* get next undo */
  287.             curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next;
  288.                                                     /* nothing to undo */
  289.         if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL)
  290.         {
  291.                                     /* stick curbuf->b_u_curhead at end */
  292.             curbuf->b_u_curhead = curbuf->b_u_oldhead;
  293.             beep_flush();
  294.             break;
  295.         }
  296.  
  297.         u_undoredo();
  298.     }
  299.     u_undo_end();
  300. }
  301.  
  302.     void
  303. u_redo(count)
  304.     int count;
  305. {
  306.     u_newcount = 0;
  307.     u_oldcount = 0;
  308.     while (count--)
  309.     {
  310.         if (curbuf->b_u_curhead == NULL || p_ul <= 0)    /* nothing to redo */
  311.         {
  312.             beep_flush();
  313.             break;
  314.         }
  315.  
  316.         u_undoredo();
  317.                                                     /* advance for next redo */
  318.         curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev;
  319.     }
  320.     u_undo_end();
  321. }
  322.  
  323. /*
  324.  * u_undoredo: common code for undo and redo
  325.  *
  326.  * The lines in the file are replaced by the lines in the entry list at
  327.  * curbuf->b_u_curhead. The replaced lines in the file are saved in the entry
  328.  * list for the next undo/redo.
  329.  */
  330.     static void
  331. u_undoredo()
  332. {
  333.     char_u        **newarray = NULL;
  334.     linenr_t    oldsize;
  335.     linenr_t    newsize;
  336.     linenr_t    top, bot;
  337.     linenr_t    lnum;
  338.     linenr_t    newlnum = MAXLNUM;
  339.     long        i;
  340.     struct u_entry *uep, *nuep;
  341.     struct u_entry *newlist = NULL;
  342.     int            old_flags;
  343.     int            new_flags;
  344.     FPOS        namedm[NMARKS];
  345.     int            empty_buffer;                /* buffer became empty */
  346.  
  347.     old_flags = curbuf->b_u_curhead->uh_flags;
  348.     new_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
  349.                ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
  350.     if (old_flags & UH_CHANGED)
  351.         CHANGED;
  352.     else
  353.         UNCHANGED(curbuf);
  354.     setpcmark();
  355.  
  356.     /*
  357.      * save marks before undo/redo
  358.      */
  359.     vim_memmove((char *)namedm, (char *)curbuf->b_namedm, 
  360.                                                        sizeof(FPOS) * NMARKS); 
  361.     curbuf->b_op_start.lnum = curbuf->b_ml.ml_line_count;
  362.     curbuf->b_op_start.col = 0;
  363.     curbuf->b_op_end.lnum = 0;
  364.     curbuf->b_op_end.col = 0;
  365.  
  366.     for (uep = curbuf->b_u_curhead->uh_entry; uep != NULL; uep = nuep)
  367.     {
  368.         top = uep->ue_top;
  369.         bot = uep->ue_bot;
  370.         if (bot == 0)
  371.             bot = curbuf->b_ml.ml_line_count + 1;
  372.         if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  373.         {
  374.             EMSG("u_undo: line numbers wrong");
  375.             CHANGED;        /* don't want UNCHANGED now */
  376.             return;
  377.         }
  378.  
  379.         if (top < newlnum)
  380.         {
  381.             newlnum = top;
  382.             curwin->w_cursor.lnum = top + 1;
  383.         }
  384.         oldsize = bot - top - 1;    /* number of lines before undo */
  385.         newsize = uep->ue_size;        /* number of lines after undo */
  386.  
  387.         empty_buffer = FALSE;
  388.  
  389.         /* delete the lines between top and bot and save them in newarray */
  390.         if (oldsize)
  391.         {
  392.             if ((newarray = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * oldsize))) == NULL)
  393.             {
  394.                 do_outofmem_msg();
  395.                 /*
  396.                  * We have messed up the entry list, repair is impossible.
  397.                  * we have to free the rest of the list.
  398.                  */
  399.                 while (uep != NULL)
  400.                 {
  401.                     nuep = uep->ue_next;
  402.                     u_freeentry(uep, uep->ue_size);
  403.                     uep = nuep;
  404.                 }
  405.                 break;
  406.             }
  407.             /* delete backwards, it goes faster in most cases */
  408.             for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum)
  409.             {
  410.                     /* what can we do when we run out of memory? */
  411.                 if ((newarray[i] = u_save_line(lnum)) == NULL)
  412.                     do_outofmem_msg();
  413.                     /* remember we deleted the last line in the buffer, and a
  414.                      * dummy empty line will be inserted */
  415.                 if (curbuf->b_ml.ml_line_count == 1)
  416.                     empty_buffer = TRUE;
  417.                 ml_delete(lnum, FALSE);
  418.             }
  419.         }
  420.  
  421.         /* insert the lines in u_array between top and bot */
  422.         if (newsize)
  423.         {
  424.             for (lnum = top, i = 0; i < newsize; ++i, ++lnum)
  425.             {
  426.                 /*
  427.                  * If the file is empty, there is an empty line 1 that we
  428.                  * should get rid of, by replacing it with the new line
  429.                  */
  430.                 if (empty_buffer && lnum == 0)
  431.                     ml_replace((linenr_t)1, uep->ue_array[i], TRUE);
  432.                 else
  433.                     ml_append(lnum, uep->ue_array[i], (colnr_t)0, FALSE);
  434.                 u_free_line(uep->ue_array[i]);
  435.             }
  436.             u_free_line((char_u *)uep->ue_array);
  437.         }
  438.  
  439.         /* adjust marks */
  440.         if (oldsize != newsize)
  441.         {
  442.             mark_adjust(top + 1, top + oldsize, MAXLNUM,
  443.                                                (long)newsize - (long)oldsize);
  444.             if (curbuf->b_op_start.lnum > top + oldsize)
  445.                 curbuf->b_op_start.lnum += newsize - oldsize;
  446.             if (curbuf->b_op_end.lnum > top + oldsize)
  447.                 curbuf->b_op_end.lnum += newsize - oldsize;
  448.         }
  449.         /* set '[ and '] mark */
  450.         if (top + 1 < curbuf->b_op_start.lnum)
  451.             curbuf->b_op_start.lnum = top + 1;
  452.         if (newsize == 0 && top + 1 > curbuf->b_op_end.lnum)
  453.             curbuf->b_op_end.lnum = top + 1;
  454.         else if (top + newsize > curbuf->b_op_end.lnum)
  455.             curbuf->b_op_end.lnum = top + newsize;
  456.  
  457.         u_newcount += newsize;
  458.         u_oldcount += oldsize;
  459.         uep->ue_size = oldsize;
  460.         uep->ue_array = newarray;
  461.         uep->ue_bot = top + newsize + 1;
  462.  
  463.         /*
  464.          * insert this entry in front of the new entry list
  465.          */
  466.         nuep = uep->ue_next;
  467.         uep->ue_next = newlist;
  468.         newlist = uep;
  469.     }
  470.  
  471.     curbuf->b_u_curhead->uh_entry = newlist;
  472.     curbuf->b_u_curhead->uh_flags = new_flags;
  473.     if ((old_flags & UH_EMPTYBUF) && bufempty())
  474.         curbuf->b_ml.ml_flags |= ML_EMPTY;
  475.  
  476.     /*
  477.      * restore marks from before undo/redo
  478.      */
  479.     for (i = 0; i < NMARKS; ++i)
  480.         if (curbuf->b_u_curhead->uh_namedm[i].lnum)
  481.         {
  482.             curbuf->b_namedm[i] = curbuf->b_u_curhead->uh_namedm[i];
  483.             curbuf->b_u_curhead->uh_namedm[i] = namedm[i];
  484.         }
  485.  
  486.     /*
  487.      * If the cursor is only off by one line, put it at the same position as
  488.      * before starting the change (for the "o" command).
  489.      * Otherwise the cursor should go to the first undone line.
  490.      */
  491.     if (curbuf->b_u_curhead->uh_cursor.lnum + 1 == curwin->w_cursor.lnum &&
  492.                                                     curwin->w_cursor.lnum > 1)
  493.         --curwin->w_cursor.lnum;
  494.     if (curbuf->b_u_curhead->uh_cursor.lnum == curwin->w_cursor.lnum)
  495.         curwin->w_cursor.col = curbuf->b_u_curhead->uh_cursor.col;
  496.     else if (curwin->w_cursor.lnum <= curbuf->b_ml.ml_line_count)
  497.         beginline(MAYBE);
  498.     /* We still seem to need the case below because sometimes we get here with
  499.      * the current cursor line being one past the end (eg after adding lines
  500.      * at the end of the file, and then undoing it).  Is it fair enough that
  501.      * this happens? -- webb
  502.      */
  503.     else
  504.         curwin->w_cursor.col = 0;
  505. }
  506.  
  507. /*
  508.  * If we deleted or added lines, report the number of less/more lines.
  509.  * Otherwise, report the number of changes (this may be incorrect
  510.  * in some cases, but it's better than nothing).
  511.  */
  512.     static void
  513. u_undo_end()
  514. {
  515.     if ((u_oldcount -= u_newcount) != 0)
  516.         msgmore(-u_oldcount);
  517.     else if (u_newcount > p_report)
  518.         smsg((char_u *)"%ld change%s", u_newcount, plural(u_newcount));
  519.  
  520.     update_curbuf(CURSUPD);        /* need to update all windows in this buffer */
  521. }
  522.  
  523. /*
  524.  * u_sync: stop adding to the current entry list
  525.  */
  526.     void
  527. u_sync()
  528. {
  529.     if (curbuf->b_u_synced)
  530.         return;                /* already synced */
  531.     u_getbot();                /* compute ue_bot of previous u_save */
  532.     curbuf->b_u_curhead = NULL;
  533. }
  534.  
  535. /*
  536.  * Called after writing the file and setting b_changed to FALSE.
  537.  * Now an undo means that the buffer is modified.
  538.  */
  539.     void
  540. u_unchanged(buf)
  541.     BUF        *buf;
  542. {
  543.     register struct u_header *uh;
  544.  
  545.     for (uh = buf->b_u_newhead; uh; uh = uh->uh_next)
  546.         uh->uh_flags |= UH_CHANGED;
  547.     buf->b_did_warn = FALSE;
  548. }
  549.  
  550. /*
  551.  * u_getbot(): compute the line number of the previous u_save
  552.  *                 It is called only when b_u_synced is FALSE.
  553.  */
  554.     static void
  555. u_getbot()
  556. {
  557.     register struct u_entry *uep;
  558.  
  559.     if (curbuf->b_u_newhead == NULL ||
  560.                                 (uep = curbuf->b_u_newhead->uh_entry) == NULL)
  561.     {
  562.         EMSG("undo list corrupt");
  563.         return;
  564.     }
  565.  
  566.     if (uep->ue_lcount != 0)
  567.     {
  568.         /*
  569.          * the new ue_bot is computed from the number of lines that has been
  570.          * inserted (0 - deleted) since calling u_save. This is equal to the old
  571.          * line count subtracted from the current line count.
  572.          */
  573.         uep->ue_bot = uep->ue_top + uep->ue_size + 1 +
  574.                                 (curbuf->b_ml.ml_line_count - uep->ue_lcount);
  575.         if (uep->ue_bot < 1 || uep->ue_bot > curbuf->b_ml.ml_line_count)
  576.         {
  577.             EMSG("undo line missing");
  578.             uep->ue_bot = uep->ue_top + 1;    /* assume all lines deleted, will
  579.                                              * get all the old lines back
  580.                                              * without deleting the current
  581.                                              * ones */
  582.         }
  583.         uep->ue_lcount = 0;
  584.     }
  585.  
  586.     curbuf->b_u_synced = TRUE;
  587. }
  588.  
  589. /*
  590.  * u_freelist: free one entry list and adjust the pointers
  591.  */
  592.     static void
  593. u_freelist(uhp)
  594.     struct u_header *uhp;
  595. {
  596.     register struct u_entry *uep, *nuep;
  597.  
  598.     for (uep = uhp->uh_entry; uep != NULL; uep = nuep)
  599.     {
  600.         nuep = uep->ue_next;
  601.         u_freeentry(uep, uep->ue_size);
  602.     }
  603.  
  604.     if (curbuf->b_u_curhead == uhp)
  605.         curbuf->b_u_curhead = NULL;
  606.  
  607.     if (uhp->uh_next == NULL)
  608.         curbuf->b_u_oldhead = uhp->uh_prev;
  609.     else
  610.         uhp->uh_next->uh_prev = uhp->uh_prev;
  611.  
  612.     if (uhp->uh_prev == NULL)
  613.         curbuf->b_u_newhead = uhp->uh_next;
  614.     else
  615.         uhp->uh_prev->uh_next = uhp->uh_next;
  616.  
  617.     u_free_line((char_u *)uhp);
  618.     --curbuf->b_u_numhead;
  619. }
  620.  
  621. /*
  622.  * free entry 'uep' and 'n' lines in uep->ue_array[]
  623.  */
  624.     static void
  625. u_freeentry(uep, n)
  626.     struct u_entry *uep;
  627.     register long n;
  628. {
  629.     while (n)
  630.         u_free_line(uep->ue_array[--n]);
  631.     u_free_line((char_u *)uep);
  632. }
  633.  
  634. /*
  635.  * invalidate the undo buffer; called when storage has already been released
  636.  */
  637.     void
  638. u_clearall(buf)
  639.     BUF        *buf;
  640. {
  641.     buf->b_u_newhead = buf->b_u_oldhead = buf->b_u_curhead = NULL;
  642.     buf->b_u_synced = TRUE;
  643.     buf->b_u_numhead = 0;
  644.     buf->b_u_line_ptr = NULL;
  645.     buf->b_u_line_lnum = 0;
  646. }
  647.  
  648. /*
  649.  * save the line "lnum" for the "U" command
  650.  */
  651.     void
  652. u_saveline(lnum)
  653.     linenr_t lnum;
  654. {
  655.     if (lnum == curbuf->b_u_line_lnum)        /* line is already saved */
  656.         return;
  657.     if (lnum < 1 || lnum > curbuf->b_ml.ml_line_count)    /* should never happen */
  658.         return;
  659.     u_clearline();
  660.     curbuf->b_u_line_lnum = lnum;
  661.     if (curwin->w_cursor.lnum == lnum)
  662.         curbuf->b_u_line_colnr = curwin->w_cursor.col;
  663.     else
  664.         curbuf->b_u_line_colnr = 0;
  665.     if ((curbuf->b_u_line_ptr = u_save_line(lnum)) == NULL)
  666.         do_outofmem_msg();
  667. }
  668.  
  669. /*
  670.  * clear the line saved for the "U" command
  671.  * (this is used externally for crossing a line while in insert mode)
  672.  */
  673.     void
  674. u_clearline()
  675. {
  676.     if (curbuf->b_u_line_ptr != NULL)
  677.     {
  678.         u_free_line(curbuf->b_u_line_ptr);
  679.         curbuf->b_u_line_ptr = NULL;
  680.         curbuf->b_u_line_lnum = 0;
  681.     }
  682. }
  683.  
  684. /*
  685.  * Implementation of the "U" command.
  686.  * Differentiation from vi: "U" can be undone with the next "U".
  687.  * We also allow the cursor to be in another line.
  688.  */
  689.     void
  690. u_undoline()
  691. {
  692.     colnr_t t;
  693.     char_u    *oldp;
  694.  
  695.     if (undo_off)
  696.         return;
  697.  
  698.     if (curbuf->b_u_line_ptr == NULL ||
  699.                         curbuf->b_u_line_lnum > curbuf->b_ml.ml_line_count)
  700.     {
  701.         beep_flush();
  702.         return;
  703.     }
  704.         /* first save the line for the 'u' command */
  705.     if (u_savecommon(curbuf->b_u_line_lnum - 1,
  706.                                 curbuf->b_u_line_lnum + 1, (linenr_t)0) == FAIL)
  707.         return;
  708.     oldp = u_save_line(curbuf->b_u_line_lnum);
  709.     if (oldp == NULL)
  710.     {
  711.         do_outofmem_msg();
  712.         return;
  713.     }
  714.     ml_replace(curbuf->b_u_line_lnum, curbuf->b_u_line_ptr, TRUE);
  715.     u_free_line(curbuf->b_u_line_ptr);
  716.     curbuf->b_u_line_ptr = oldp;
  717.  
  718.     t = curbuf->b_u_line_colnr;
  719.     if (curwin->w_cursor.lnum == curbuf->b_u_line_lnum)
  720.         curbuf->b_u_line_colnr = curwin->w_cursor.col;
  721.     curwin->w_cursor.col = t;
  722.     curwin->w_cursor.lnum = curbuf->b_u_line_lnum;
  723.     cursupdate();
  724.     updateScreen(VALID_TO_CURSCHAR);
  725. }
  726.  
  727. /*
  728.  * storage allocation for the undo lines and blocks of the current file
  729.  */
  730.  
  731. /*
  732.  * Memory is allocated in relatively large blocks. These blocks are linked
  733.  * in the allocated block list, headed by curbuf->b_block_head. They are all freed
  734.  * when abandoning a file, so we don't have to free every single line. The
  735.  * list is kept sorted on memory address.
  736.  * block_alloc() allocates a block.
  737.  * m_blockfree() frees all blocks.
  738.  *
  739.  * The available chunks of memory are kept in free chunk lists. There is
  740.  * one free list for each block of allocated memory. The list is kept sorted
  741.  * on memory address.
  742.  * u_alloc_line() gets a chunk from the free lists.
  743.  * u_free_line() returns a chunk to the free lists.
  744.  * curbuf->b_m_search points to the chunk before the chunk that was
  745.  * freed/allocated the last time.
  746.  * curbuf->b_mb_current points to the b_head where curbuf->b_m_search
  747.  * points into the free list.
  748.  *
  749.  *
  750.  *  b_block_head     /---> block #1     /---> block #2
  751.  *       mb_next ---/       mb_next ---/       mb_next ---> NULL
  752.  *       mb_info            mb_info            mb_info
  753.  *          |                  |                  |
  754.  *          V                  V                  V
  755.  *        NULL          free chunk #1.1      free chunk #2.1
  756.  *                             |                  |
  757.  *                             V                  V
  758.  *                      free chunk #1.2          NULL
  759.  *                             |
  760.  *                             V
  761.  *                            NULL
  762.  *
  763.  * When a single free chunk list would have been used, it could take a lot
  764.  * of time in u_free_line() to find the correct place to insert a chunk in the
  765.  * free list. The single free list would become very long when many lines are
  766.  * changed (e.g. with :%s/^M$//).
  767.  */
  768.  
  769.     /*
  770.      * this blocksize is used when allocating new lines
  771.      */
  772. #define MEMBLOCKSIZE 2044
  773.  
  774. /*
  775.  * The size field contains the size of the chunk, including the size field itself.
  776.  *
  777.  * When the chunk is not in-use it is preceded with the m_info structure.
  778.  * The m_next field links it in one of the free chunk lists.
  779.  *
  780.  * On most unix systems structures have to be longword (32 or 64 bit) aligned.
  781.  * On most other systems they are short (16 bit) aligned.
  782.  */
  783.  
  784. /* the structure definitions are now in structs.h */
  785.  
  786. #ifdef ALIGN_LONG
  787.     /* size of m_size */
  788. # define M_OFFSET (sizeof(long_u))
  789. #else
  790.     /* size of m_size */
  791. # define M_OFFSET (sizeof(short_u))
  792. #endif
  793.  
  794. /*
  795.  * Allocate a block of memory and link it in the allocated block list.
  796.  */
  797.     static char_u *
  798. u_blockalloc(size)
  799.     long_u    size;
  800. {
  801.     struct m_block *p;
  802.     struct m_block *mp, *next;
  803.  
  804.     p = (struct m_block *)lalloc(size + sizeof(struct m_block), FALSE);
  805.     if (p != NULL)
  806.     {
  807.          /* Insert the block into the allocated block list, keeping it
  808.                      sorted on address. */
  809.         for (mp = &curbuf->b_block_head; (next = mp->mb_next) != NULL && next < p; mp = next)
  810.             ;
  811.         p->mb_next = next;                /* link in block list */
  812.         mp->mb_next = p;
  813.         p->mb_info.m_next = NULL;        /* clear free list */
  814.         p->mb_info.m_size = 0;
  815.         curbuf->b_mb_current = p;        /* remember current block */
  816.         curbuf->b_m_search = NULL;
  817.         p++;                            /* return usable memory */
  818.     }
  819.     return (char_u *)p;
  820. }
  821.  
  822. /*
  823.  * free all allocated memory blocks for the buffer 'buf'
  824.  */
  825.     void
  826. u_blockfree(buf)
  827.     BUF        *buf;
  828. {
  829.     struct m_block    *p, *np;
  830.  
  831.     for (p = buf->b_block_head.mb_next; p != NULL; p = np)
  832.     {
  833.         np = p->mb_next;
  834.         vim_free(p);
  835.     }
  836.     buf->b_block_head.mb_next = NULL;
  837.     buf->b_m_search = NULL;
  838.     buf->b_mb_current = NULL;
  839. }
  840.  
  841. /*
  842.  * Free a chunk of memory.
  843.  * Insert the chunk into the correct free list, keeping it sorted on address.
  844.  */
  845.     static void
  846. u_free_line(ptr)
  847.     char_u *ptr;
  848. {
  849.     register info_t        *next;
  850.     register info_t        *prev, *curr;
  851.     register info_t        *mp;
  852.     struct m_block        *nextb;
  853.  
  854.     if (ptr == NULL || ptr == IObuff)
  855.         return;    /* illegal address can happen in out-of-memory situations */
  856.  
  857.     mp = (info_t *)(ptr - M_OFFSET);
  858.  
  859.         /* find block where chunk could be a part off */
  860.         /* if we change curbuf->b_mb_current, curbuf->b_m_search is set to NULL */
  861.     if (curbuf->b_mb_current == NULL || mp < (info_t *)curbuf->b_mb_current)
  862.     {
  863.         curbuf->b_mb_current = curbuf->b_block_head.mb_next;
  864.         curbuf->b_m_search = NULL;
  865.     }
  866.     if ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  867.     {
  868.         curbuf->b_mb_current = nextb;
  869.         curbuf->b_m_search = NULL;
  870.     }
  871.     while ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  872.         curbuf->b_mb_current = nextb;
  873.  
  874.     curr = NULL;
  875.     /*
  876.      * If mp is smaller than curbuf->b_m_search->m_next go to the start of
  877.      * the free list
  878.      */
  879.     if (curbuf->b_m_search == NULL || mp < (curbuf->b_m_search->m_next))
  880.         next = &(curbuf->b_mb_current->mb_info);
  881.     else
  882.         next = curbuf->b_m_search;
  883.     /*
  884.      * The following loop is executed very often.
  885.      * Therefore it has been optimized at the cost of readability.
  886.      * Keep it fast!
  887.      */
  888. #ifdef SLOW_BUT_EASY_TO_READ
  889.     do
  890.     {
  891.         prev = curr;
  892.         curr = next;
  893.         next = next->m_next;
  894.     }
  895.     while (mp > next && next != NULL);
  896. #else
  897.     do                                        /* first, middle, last */
  898.     {
  899.         prev = next->m_next;                /* curr, next, prev */
  900.         if (prev == NULL || mp <= prev)
  901.         {
  902.             prev = curr;
  903.             curr = next;
  904.             next = next->m_next;
  905.             break;
  906.         }
  907.         curr = prev->m_next;                /* next, prev, curr */
  908.         if (curr == NULL || mp <= curr)
  909.         {
  910.             prev = next;
  911.             curr = prev->m_next;
  912.             next = curr->m_next;
  913.             break;
  914.         }
  915.         next = curr->m_next;                /* prev, curr, next */
  916.     }
  917.     while (mp > next && next != NULL);
  918. #endif
  919.  
  920. /* if *mp and *next are concatenated, join them into one chunk */
  921.     if ((char_u *)mp + mp->m_size == (char_u *)next)
  922.     {
  923.         mp->m_size += next->m_size;
  924.         mp->m_next = next->m_next;
  925.     }
  926.     else
  927.         mp->m_next = next;
  928.  
  929. /* if *curr and *mp are concatenated, join them */
  930.     if (prev != NULL && (char_u *)curr + curr->m_size == (char_u *)mp)
  931.     {
  932.         curr->m_size += mp->m_size;
  933.         curr->m_next = mp->m_next;
  934.         curbuf->b_m_search = prev;
  935.     }
  936.     else
  937.     {
  938.         curr->m_next = mp;
  939.         curbuf->b_m_search = curr;    /* put curbuf->b_m_search before freed chunk */
  940.     }
  941. }
  942.  
  943. /*
  944.  * Allocate and initialize a new line structure with room for at least
  945.  * 'size' characters plus a terminating NUL.
  946.  */
  947.     static char_u *
  948. u_alloc_line(size)
  949.     register unsigned size;
  950. {
  951.     register info_t *mp, *mprev, *mp2;
  952.     struct m_block    *mbp;
  953.     int                 size_align;
  954.  
  955. /*
  956.  * Add room for size field and trailing NUL byte.
  957.  * Adjust for minimal size (must be able to store info_t
  958.  * plus a trailing NUL, so the chunk can be released again)
  959.  */
  960.     size += M_OFFSET + 1;
  961.     if (size < sizeof(info_t) + 1)
  962.       size = sizeof(info_t) + 1;
  963.  
  964. /*
  965.  * round size up for alignment
  966.  */
  967.     size_align = (size + ALIGN_MASK) & ~ALIGN_MASK;
  968.  
  969. /*
  970.  * If curbuf->b_m_search is NULL (uninitialized free list) start at
  971.  * curbuf->b_block_head
  972.  */
  973.     if (curbuf->b_mb_current == NULL || curbuf->b_m_search == NULL)
  974.     {
  975.         curbuf->b_mb_current = &curbuf->b_block_head;
  976.         curbuf->b_m_search = &(curbuf->b_block_head.mb_info);
  977.     }
  978.  
  979. /* search for space in free list */
  980.     mprev = curbuf->b_m_search;
  981.     mbp = curbuf->b_mb_current;
  982.     mp = curbuf->b_m_search->m_next;
  983.     if (mp == NULL)
  984.     {
  985.         if (mbp->mb_next)
  986.             mbp = mbp->mb_next;
  987.         else
  988.             mbp = &curbuf->b_block_head;
  989.         mp = curbuf->b_m_search = &(mbp->mb_info);
  990.     }
  991.     while (mp->m_size < size)
  992.     {
  993.         if (mp == curbuf->b_m_search)        /* back where we started in free chunk list */
  994.         {
  995.             if (mbp->mb_next)
  996.                 mbp = mbp->mb_next;
  997.             else
  998.                 mbp = &curbuf->b_block_head;
  999.             mp = curbuf->b_m_search = &(mbp->mb_info);
  1000.             if (mbp == curbuf->b_mb_current)    /* back where we started in block list */
  1001.             {
  1002.                 int        n = (size_align > (MEMBLOCKSIZE / 4) ? size_align : MEMBLOCKSIZE);
  1003.  
  1004.                 mp = (info_t *)u_blockalloc((long_u)n);
  1005.                 if (mp == NULL)
  1006.                     return (NULL);
  1007.                 mp->m_size = n;
  1008.                 u_free_line((char_u *)mp + M_OFFSET);
  1009.                 mp = curbuf->b_m_search;
  1010.                 mbp = curbuf->b_mb_current;
  1011.             }
  1012.         }
  1013.         mprev = mp;
  1014.         if ((mp = mp->m_next) == NULL)        /* at end of the list */
  1015.             mp = &(mbp->mb_info);            /* wrap around to begin */
  1016.     }
  1017.  
  1018. /* if the chunk we found is large enough, split it up in two */
  1019.     if ((long)mp->m_size - size_align >= (long)(sizeof(info_t) + 1))
  1020.     {
  1021.         mp2 = (info_t *)((char_u *)mp + size_align);
  1022.         mp2->m_size = mp->m_size - size_align;
  1023.         mp2->m_next = mp->m_next;
  1024.         mprev->m_next = mp2;
  1025.         mp->m_size = size_align;
  1026.     }
  1027.     else                    /* remove *mp from the free list */
  1028.     {
  1029.         mprev->m_next = mp->m_next;
  1030.     }
  1031.     curbuf->b_m_search = mprev;
  1032.     curbuf->b_mb_current = mbp;
  1033.  
  1034.     mp = (info_t *)((char_u *)mp + M_OFFSET);
  1035.     *(char_u *)mp = NUL;                    /* set the first byte to NUL */
  1036.  
  1037.     return ((char_u *)mp);
  1038. }
  1039.  
  1040. /*
  1041.  * u_save_line(): allocate memory with u_alloc_line() and copy line 'lnum' into it.
  1042.  */
  1043.     static char_u *
  1044. u_save_line(lnum)
  1045.     linenr_t    lnum;
  1046. {
  1047.     register char_u *src;
  1048.     register char_u *dst;
  1049.     register unsigned len;
  1050.  
  1051.     src = ml_get(lnum);
  1052.     len = STRLEN(src);
  1053.     if ((dst = u_alloc_line(len)) != NULL)
  1054.         vim_memmove(dst, src, (size_t)(len + 1));
  1055.     return (dst);
  1056. }
  1057.